package com.gaogzhen.datastructure.graph.undirected;

import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.ST;

/**
 * 符号图
 * @author: Administrator
 * @createTime: 2023/03/14 19:59
 */
public class SymbolGraph {
    /**
     * 符号表
     * 符号名-索引
     */
    private ST<String, Integer> st;

    /**
     * 反向索引数组
     * 索引->符号名
     */
    private String[] keys;

    /**
     * 无向图
     */
    private Graph graph;

    /**
     * 文件读入数据构建无向图
     * @param filename  文件路径
     * @param delimiter 顶点分隔符
     */
    public SymbolGraph(String filename, String delimiter) {
        // 构建符号表
        st = new ST<>();
        In in = new In(filename);
        while (!in.isEmpty()) {
            String[] s = in.readLine().split(delimiter);
            for (int i = 0; i < s.length; i++) {
                if (!st.contains(s[i])) {
                    st.put(s[i], st.size());
                }
            }
        }
        // 初始化反向索引数组keys
        keys = new String[st.size()];
        for (String name : st.keys()) {
            keys[st.get(name)] = name;
        }
        // 构建无向图
        graph = new Graph(st.size());
        in = new In(filename);
        while (in.hasNextLine()) {
            String[] a = in.readLine().split(delimiter);
            int v = st.get(a[0]);
            for (int i = 1; i < a.length; i++) {
                int w = st.get(a[i]);
                graph.addEdge(v, w);
            }
        }
    }

    /**
     * 是否包含某个顶点
     * @param s   给定顶点
     * @return {@code true} 如果顶点 {@code s}在符号表中；否则 {@code false}
     */
    public boolean contains(String s) { return st.contains(s);}

    /**
     * 返回顶点名称对应的索引
     * @param s 顶点名称
     * @return 顶点名称 {@code s} 对应的索引(0~V-1)
     */
    public int indexOf(String s) {
        return st.get(s);
    }

    /**
     * 返回索引{@code v}对应的顶点名称
     * @param v 顶点索引(0~V-1)
     * @return  索引 {@code v} 对应的顶点名称
     */
    public String nameOf(int v) {
        validateVertex(v);
        return keys[v];
    }

    /**
     * 返回该符号图关联的无向图
     * @return  该符号图关联的无向图
     */
    public Graph graph() {
        return graph;
    }

    /**
     * 校验顶点 {@code v} 是否合法
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int c = graph.V();
        if (v < 0 || v >= c) {
            throw new IllegalArgumentException("顶点 " + v + " 不在 0~" + (c - 1) + " 之间");
        }
    }
}
